<html>
<head><meta charset="utf-8"><title>Help with threads · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html">Help with threads</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="238981356"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238981356" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Oliver E. Anderson <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238981356">(May 16 2021 at 14:10)</a>:</h4>
<p>I am doing an expensive calculation, and using threads isn't helping at all, so I am wondering if I am doing something wrong. <br>
Here is the single threaded version:</p>
<div class="codehilite"><pre><span></span><code>pub fn is_square_free(n: u128) -&gt; bool {
    const MAX: u128 = 2_u128.pow(126);
    if n &gt; MAX {
        panic!(&quot;cannot work with numbers larger that {} \r\n&quot;, MAX);
    }
    // Enough to test 4 followed by all odd squares that are less than n.
    !iter::once(2_u128)
        .chain((3..n).into_iter().step_by(2))
        .map(|i| i.pow(2))
        .take_while(|i| i &lt;= &amp;n)
        .any(|i| (n % i) == 0)
}
</code></pre></div>
<p>and here is my attempt at making a threaded version:</p>
<div class="codehilite"><pre><span></span><code>fn is_square_free_piece(n: u128, from: u128, to: u128) -&gt; bool {
    if from &lt;= 2 &amp;&amp; ((n % 4) == 0) {
        return false;
    }
    !(from..to)
        .into_iter()
        .step_by(2)
        .map(|i| i.pow(2))
        .take_while(|i| (i &lt;= &amp;n))
        .any(|i| (n % i) == 0)
}


pub fn concurrent_is_square_free(n: u128, num_threads: u32) -&gt; bool {
    let num_threads = num_threads as u128;
    let (sender, receiver) = std::sync::mpsc::channel();
    let iter = (1_u128..=num_threads).into_iter();
    let elements_per_thread = n/(num_threads);
    for i in iter {
        let from = (i-1) *elements_per_thread + 2;
        let to = if i != num_threads {i * elements_per_thread + 2}else {n};
        let sender_clone = sender.clone();
        std::thread::spawn(move || {
            if !is_square_free_piece(n, from, to){
                sender_clone.send(false).unwrap();
            }
            drop(sender_clone);
        });
    }
    drop(sender);

    if receiver.recv().is_ok(){
        false
    } else {
        true
    }
}
</code></pre></div>
<p>when n = 2_u128.pow(65) - 49, the single threaded and the multi-threaded take approximately the same amount of time (around 65 seconds on my computer), and this is the case no matter how few or many threads i choose. Can anyone please tell me what I am doing wrong, or explain why this task is not faster with threads?</p>



<a name="238981941"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238981941" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Oliver E. Anderson <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238981941">(May 16 2021 at 14:20)</a>:</h4>
<p>If it is of any help here is a snippet of what the <code>lscpu</code>command yields:</p>
<div class="codehilite"><pre><span></span><code>$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
</code></pre></div>



<a name="238982116"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982116" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982116">(May 16 2021 at 14:24)</a>:</h4>
<p>How many threads are you using?</p>



<a name="238982179"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982179" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Oliver E. Anderson <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982179">(May 16 2021 at 14:24)</a>:</h4>
<p><span class="user-mention silent" data-user-id="203546">Laurențiu</span> <a href="#narrow/stream/122651-general/topic/Help.20with.20threads/near/238982116">said</a>:</p>
<blockquote>
<p>How many threads are you using?</p>
</blockquote>
<p>I have tried with 2, 4 ,6 and 8. All take about the same amount of time.</p>



<a name="238982289"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982289" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Oliver E. Anderson <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982289">(May 16 2021 at 14:26)</a>:</h4>
<p>I also tried using the channel from crossbeam, but that didn't speed things up at all. When using par_iter from the rayon crate I get about 3x the performance, but those iterators don't allow me to call .step_by which is why I tried parallelizing my implementation myself.</p>



<a name="238982746"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982746" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982746">(May 16 2021 at 14:34)</a>:</h4>
<p>Your first thread does all the work</p>



<a name="238982830"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982830" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Oliver E. Anderson <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982830">(May 16 2021 at 14:34)</a>:</h4>
<p><span class="user-mention silent" data-user-id="203546">Laurențiu</span> <a href="#narrow/stream/122651-general/topic/Help.20with.20threads/near/238982746">said</a>:</p>
<blockquote>
<p>Your first thread does all the work</p>
</blockquote>
<p>Why?</p>



<a name="238982850"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982850" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982850">(May 16 2021 at 14:35)</a>:</h4>
<p>Because <code>i</code> goes only to <code>sqrt(n)</code>, while <code>from..to</code> covers <code>2..n</code></p>



<a name="238982884"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982884" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Oliver E. Anderson <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982884">(May 16 2021 at 14:35)</a>:</h4>
<p><span class="user-mention silent" data-user-id="203546">Laurențiu</span> <a href="#narrow/stream/122651-general/topic/Help.20with.20threads/near/238982850">said</a>:</p>
<blockquote>
<p>Because <code>i</code> goes only to <code>sqrt(n)</code>, while <code>from..to</code> covers <code>1..n</code></p>
</blockquote>
<p>Lol silly me. Thank you for your help :) Will try to think a bit harder before I ask the next time.</p>



<a name="238982947"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982947" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982947">(May 16 2021 at 14:36)</a>:</h4>
<p>So if <code>sqrt(n) &lt; n / num_threads</code> (or <code>num_threads &lt; sqrt(n)</code>), the first thread does everything, while the rest stop at the first number. You can see this easily if you add some log messages when a thread starts and stops.</p>



<a name="238982992"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238982992" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238982992">(May 16 2021 at 14:36)</a>:</h4>
<p>Try splitting <code>[2; sqrt(n)]</code> into <code>num_threads</code> intervals</p>



<a name="238983269"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238983269" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Oliver E. Anderson <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238983269">(May 16 2021 at 14:41)</a>:</h4>
<p><span class="user-mention silent" data-user-id="203546">Laurențiu</span> <a href="#narrow/stream/122651-general/topic/Help.20with.20threads/near/238982992">said</a>:</p>
<blockquote>
<p>Try splitting <code>[2; sqrt(n)]</code> into <code>num_threads</code> intervals</p>
</blockquote>
<p>That made almost a 6 x improvement. Thank you :)</p>



<a name="238983354"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/238983354" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#238983354">(May 16 2021 at 14:42)</a>:</h4>
<p>Seems reasonable for a 4C8T CPU</p>



<a name="239030609"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Help%20with%20threads/near/239030609" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Help.20with.20threads.html#239030609">(May 17 2021 at 04:05)</a>:</h4>
<p>This is also a good reason to use something like rayon to do the split for you.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>